// leetcode.algorithms.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <stack>
#include <queue>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <unordered_map>

using namespace std;

struct TreeNode {
  int val;
  TreeNode* left;
  TreeNode* right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};

class tree_solution
{
public:
  int maxDepth(TreeNode* root) {
    stack<TreeNode> s;
    while (root->left)
    {
      if (root->left) root = root->left;
      if (root->right) {
        root = root->left;
      }
    }
  }

  bool isSymmetric(TreeNode* left, TreeNode* right) {
    if (left == nullptr && right == nullptr)
      return true;

    if (left == nullptr || right == nullptr || left->val != right->val)
      return false;
    return isSymmetric(left->left, right->right) && isSymmetric(left->right, right->left);
  }

  bool isSymmetric(TreeNode* root) {
    if (root == nullptr)
      return true;
    return isSymmetric(root->left, root->right);
  }

  vector<vector<int>> levelOrder(TreeNode* root) {
    queue<TreeNode*> s;
    vector< vector<int> > s_level;
    if (root != nullptr) s.push(root);
    else return s_level;
    while (!s.empty()) {
      vector<int> level;
      int cnt = s.size();
      while (cnt--) {
        TreeNode* node = s.front();
        s.pop();
        level.push_back(node->val);
        if (node->left != nullptr) s.push(node->left);
        if (node->right != nullptr) s.push(node->right);
      }
      s_level.push_back(level);
    }
    return s_level;
  }

  vector<int> postOrderTraversal(TreeNode* root)
  {
    vector<int> out;
    stack<TreeNode*> s;
    if (root != nullptr) s.push(root);
    while (!s.empty())
    {
      TreeNode* node = s.top();
      if (node->right) s.push(node->right);
      if (node->right) s.push(node->right);
      out.push_back(node->val);
      s.pop();
    }
    return out;
  }

  vector<int> inOrderTraversal(TreeNode* root)
  {
    vector<int> out;
    stack<TreeNode*> s;
    TreeNode* p = root;
    while (!s.empty() || p != nullptr)
    {
      if (p != nullptr)
      {
        s.push(p);
        p = p->left;
      }
      else
      {
        p = s.top();
        s.pop();
        out.push_back(p->val);
        p = p->right;
      }
    }
    return out;
  }

  vector<int> preOrderTraversal(TreeNode* root)
  {
    vector<int> out;
    stack<TreeNode*> s;
    if (root != nullptr) s.push(root);
    while (!s.empty())
    {
      TreeNode* node = s.top();
      out.push_back(node->val);
      s.pop();
      if (node->right) s.push(node->right);
      if (node->left) s.push(node->left);
    }
    return out;
  }
};